package cn.leonis.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author Tobi
 * @Date 2021-07-10 下午5:26
 */
public class TwoNumberSumSolution {

    public static void main(String[] args) {
        int[] nums = new int[]{2, 1, 3, 4, 7};
        TwoNumberSumSolution solution = new TwoNumberSumSolution();
        int[] result = solution.twoSum2(nums, 6);
        if (result != null) {
            System.out.println(result[0]);
            System.out.println(result[1]);
        }
    }

    /**
     * 解法一：使用双重循环
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length <= 1) {
            return null;
        }
        if (nums.length == 2) {
            return nums[0] + nums[1] == target ? new int[]{0, 1} : null;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    /**
     * 高分解法
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum1(int[] nums, int target) {
        int[] res = new int[2];
        int len = nums.length;
        for (int i = 0; i < len; ++i) {
            for (int j = len - 1; j > i; --j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
                if (nums[len - i - 1] + nums[j] == target) {
                    return new int[]{j, len - i - 1};
                }
            }
        }
        return null;
    }

    /**
     * 使用HashMap来存储
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        if (nums == null || nums.length <= 1) {
            return null;
        }
        if (nums.length == 2) {
            return nums[0] + nums[1] == target ? new int[]{0, 1} : null;
        }
        // 键 存储 数值，值 存储 位置
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }

        return null;
    }
}
